The present invention relates to the field of binary data correlation and more specifically to correlation coprocessors. Digital correlation is the process of establishing the degree of similarity between two digital sequences by counting the number of bits which are the same in the two sequences. For example, the 9-bit sequences "010010101" and "011010110" have a correlation coefficient of 6, meaning that they are the same in 6 of the 9-bit positions. The correlation coefficient is dependent on the alignment of the two sequences, so that if the second sequence is rotated right one bit, to become "00101011", the correlation coefficient falls to 4. An incoming stream of data may be correlated with one or more predetermined sequences to determine which of them is embedded in the data stream, and where. Or, a data stream may be compared with itself to detect periodic patterns, and to establish the length of these patterns. Alternatively, two incoming data streams may be compared to each other to determine the degree to which they match, and to determine the optimum synchronization alignment between them. PG,4
A number of VLSI correlation integrated circuits have been developed over the past decade. To minimize correlation delay for extremely time-critical applications such as radar, the logic incorporated in these chips calculates a correlation score using a parallel adder, so for each correlation clock cycle, typically 50 ns, the correlator calculates the score for the next alignment of input data and the reference pattern. Therefore the number of input bits to the adder must be as large as the length of the sequences to be correlated. Current correlation integrated circuits can typically handle 64 to 256 bits of data at a time. If longer sequences must be correlated, more hardware is required.
Consider, for example, a data processing application in which a binary data stream is coming in from a radar or some other high data-rate source at 10 Mbps (10 million bits per second). Every time a new bit comes in, the preceding 100 bits of the data stream have to be correlated with a given 100-bit reference pattern. The chip is initially loaded with the reference pattern, and then the data stream is fed in at 10 Mbps. Every 100 ns a new bit is clocked into the chip. The same clock also shifts the last 99 bits inside the chip, and 100 comparators inside the chip each generate a "1" for each bit that matches or a "0" signal for each bit that does not match. Then a large adder array sums the number of "1" signals, and the correlation coefficient appears in binary on 7 parallel output lines (perhaps on the next clock pulse, 100 ns later). So every 100 ns, which is the bit time of the data, one new correlation coefficient is calculated. Thus a 100-bit sliding window of the data is correlated with a predefined bit sequence, in real time. The numbers of this example may be applicable to a radar application, and current chip technology supports this kind of processing speed.
However, there are circumstances where it is necessary to correlate much longer sequences of data which may have been previously captured and stored in computer memory, or which arrives at a much lower data rate. Consider, for example, an acoustic application, in which the data is coming in at 10 kbps (10 thousand bits per second, or 1,000 times slower than the radar example mentioned above) and it is desired to correlate a 10,000-bit pattern (100 times longer than before). If the previous approach is merely expanded, 100 times as many chips will be needed, each running at 1/1000 the speed of which it is capable.
Moreover, while prior art correlation processors calculate the correlation between incoming serial data and a predefined reference sequence, in many correlation applications the reference pattern is not known in advance; repetitions within the incoming data itself have to be analyzed. The approximate length (for example, 10,000 bits) of the repeating pattern is known, but doppler effects can shorten or lengthen it. To correct for this effect, the actual pattern length must be determined, so the last 9,990 bits are correlated with the preceding 9,990; the last 9,991 bits with the preceding 9,991; . . . and the last 10,010 bits with the preceding 10,010. This does not need to be done for every new bit that comes in, just once per pattern block of 10,000 bits; 10,000 scores are not needed for every 10,000 bits, just 20 or so, to track the doppler error. After the doppler correction is determined for a block of data, it is also possible to reprocess the same data in order to identify other repetition patterns in the data.
Thus, there is a need for VLSI correlation processing hardware that can economically address acoustic and other applications requiring the correlation of long sequences of binary data.